# 给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
#
#  示例 1:
#
#  输入: n = 12
# 输出: 3
# 解释: 12 = 4 + 4 + 4.
#
#  示例 2:
#
#  输入: n = 13
# 输出: 2
# 解释: 13 = 4 + 9.
#  Related Topics 广度优先搜索 数学 动态规划
#  👍 580 👎 0


# leetcode submit region begin(Prohibit modification and deletion)
class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        # dp = [i for i in range(0, n + 1)]
        #
        # for k in range(2, n + 1):
        #
        #     j = 1
        #     while j * j <= k:
        #         dp[k] = min(dp[k], 1 + dp[k - j * j])
        #         j += 1
        #
        # return dp[n]

        dp = [i for i in range(0, n + 1)]

        for j in range(2, n + 1):

            i = 1
            sq = i
            while sq <= j:
                dp[j] = min(dp[j], dp[j - sq] + 1)
                i += 1
                sq = i * i

        return dp[n]

        # leetcode submit region end(Prohibit modification and deletion)


print(Solution().numSquares(12))
